CS229：10-SVM（一）概念

_SVM_，指的是支持向量机（_support vector machines_）。

支持向量机，假设数据是线性可分的，那么我们就能找到一个超平面，将数据分成两类。但是一旦线性可分，我们就可能找到无数的超平面，都可以将数据分成两类：

但是很明显，上图中虽然a, c都对数据进行了有效的分割。但很明显，都不如b分割的好。

我们可以用“间隔”这个概念来定义这个超平面（在二维上是线）对数据的分割优劣。在分类正确的情况下，间隔越大，我们认为对数据的分类越好。

我们的目标是得到数据的分类：$y \in \lbrace -1, +1 \rbrace$。

这个超平面，则可以表示成$w^Tx+b$，其中$w=[\theta_1, \ldots, \theta_n]^T, b=\theta_0$。这个超平面可以表达成一个$n+1$维向量。

判别函数：

$$g(z)=\begin{cases} +1, & \text{如果$z\geq0$} \\\ -1, & \text{otherwise} \end{cases}$$

假设则可以表示成：$h_{w,b}(x)=g(w^Tx+b)$

间隔

函数间隔（functional margin）

某个超平面$(w,b)$和训练样本$(x^{(i)}, y^{(i)})$之间的函数间隔被表示成：

$$\hat{\gamma}^{(i)}=y^{(i)}(w^Tx^{(i)}+b)$$

于是，我们可以知道：

1. 当$y^{(i)}=1$，于是我们想获得更大的函数间隔（这是我们的目标），就需要使得$w^Tx^{(i)}+b \gg 0$
2. 相反，当$y^{(i)}=-1$，我们想获得更大的函数间隔，就需要使得$w^Tx^{(i)}+b \ll 0$

并且，很明显，只有当函数间隔$\hat{\gamma}>0$时，分类结果是正确的。

最后，超平面与数据集$\lbrace (x^{(1)}, y^{(1)}), (x^{(2)}, y^{(2)}), \ldots \rbrace$之间的函数间隔，被定义为所有函数间隔中的最小值：

$$\hat{\gamma}=\min_i\hat{\gamma}^{(i)}$$

几何间隔（geometric margin）

从点$(x^{(i)}, y^{(i)})$出发，对超平面做垂线，得到点 D，我们知道他们之间的距离，就是该超平面到数据点$(x^{(i)}, y^{(i)})$的几何间隔。

经过推导，D 的坐标可以表示为：

$$x^{(i)}-\gamma^{(i)}\frac{w}{||w||}$$

又因为，D 在超平面$w^Tx+b=0$上，所以：

$$\begin{align} & w^T(x^{(i)}-\gamma^{(i)}\frac{w}{||w||})+b=0 \\\ & \Rightarrow w^Tx^{(i)}+b=\gamma^{(i)} \cdot \frac{w^Tw}{||w||}=\gamma^{(i)} \cdot ||w|| \\\ & \Rightarrow \gamma^{(i)}=(\frac{w}{||w||})^T \cdot x^{(i)}+\frac{b}{||w||} \end{align}$$

加上正负分类的判断：

$$\gamma^{(i)}=y^{(i)} \cdot ((\frac{w}{||w||})^T \cdot x^{(i)}+\frac{b}{||w||})$$

我们可以看到，几何间隔跟函数间隔之间存在如下的关系：

$$\hat{\gamma}^{(i)} = \frac{\gamma^{(i)}}{||w||}$$

同样的，超平面与数据集$\lbrace (x^{(1)}, y^{(1)}), (x^{(2)}, y^{(2)}), \ldots \rbrace$之间的几何间隔，被定义为所有几何间隔中的最小值：

$$\gamma=\min_i\gamma^{(i)}$$

最后，我们导出最优间隔分类器（_Optimal Margin Classifier_）问题：选择$w, b$，最大化$\gamma$，同时满足$\forall(x^{(i)}, y^{(i)})$，$ y^{(i)} \cdot ((\frac{w}{||w||})^T \cdot x^{(i)}+\frac{b}{||w||}) \geq \gamma$（所有数据点的几何间隔都大于该最小几何间隔）。

目前为止，已经是 SVM 问题的一个简化版本。